This invention relates to data compression, and in particular to a hardware architecture that can be used to achieve data compression in accordance with the Lempel-Ziv compression algorithm.
When transmitting data over a communications channel, or when storing data, it is often useful to be able to compress the data, in order to reduce the resources required to transmit or store the data. Data compression techniques rely on the fact that most useful data contains patterns, which can be exploited in order to reduce the amount of data required in order to represent the source data. For example, when the source data contains one or more repeated sequences of characters, each of these can be represented more efficiently by a particular code. Provided of course that the code contains fewer bits of data than the sequence of characters, this representation reduces the amount of data required to represent the source data.
One well known data compression algorithm is the Lempel-Ziv data compression algorithm, originally described in the paper “A Universal Algorithm for Sequential Data Compression”, Jacob Ziv and Abraham Lempel, IEEE Transactions on Information Theory, vol. IT-23, no. 3, May 1977, pages 337–343. In use of the Lempel-Ziv algorithm, a code dictionary is built up, based on the received data string. The received data can for example represent text made up of characters. Then, the available codes can be assigned to respective character strings, as they appear in the received text.
In practice, this is achieved by comparing received character strings with previously received character strings. More specifically, it is necessary to find the longest of the previously received character strings that can be matched with a newly received character string. The next character of the newly received character string is then combined with that longest of the previously received character strings to form a character string that can be represented by a new code.
It is known to provide a hardware apparatus for comparing received data with previously received character strings.
For example, U.S. Pat. No. 5,003,307 to Whiting et al discloses an apparatus comprising a shift register. A newly received character is input to a first stage of the shift register. At the same time, the newly received character is compared with the characters stored in the other stages of the shift register. Logic circuitry is used to identify stages in the shift register at which the newly received character matches the stored characters. This process continues until the string of newly received characters no longer matches the strings of previously received characters at any of the stages of the shift register. At that time, the new code is output.
However, this architecture has the disadvantage that, when a match occurs, the encoding process has to stop for one clock cycle while a new search is started. This reduces the speed at which data can be processed by the device.
Jung and Burleson, in the paper “Efficient VLSI for Lempel-Ziv Compression in Wireless Data Communication Networks”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 6, no. 3, September 1998 propose an alternative architecture. However, it is desirable to improve the speed of operation of a compression architecture.